/**
 * 34. 在排序数组中查找元素的第一个和最后一个位置
 * https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
 */

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
function searchRange(nums, target) {
  const { length } = nums;
  let left = 0;
  let right = length - 1;
  let index = -1;
  while (left <= right) {
    const middle = Math.floor((left + right) / 2);
    const middleVal = nums[middle];
    if (middleVal === target) {
      index = middle;
      break;
    }
    if (middleVal > target) {
      right = middle - 1;
    } else {
      left = middle + 1;
    }
  }
  if (index < 0) return [-1, -1];
  left = index - 1;
  while (left >= 0 && nums[left] === target) {
    left -= 1;
  }
  right = index + 1;
  while (right < length && nums[right] === target) {
    right += 1;
  }
  return [left + 1, right - 1];
}

console.log(searchRange([5, 7, 7, 8, 8, 10], 8).join(',') === '3,4');
console.log(searchRange([5, 7, 7, 8, 8, 10], 6).join(',') === '-1,-1');
console.log(searchRange([], 0).join(',') === '-1,-1');
